package bfsAndDfs

// BFS-拓扑排序
func checkIfPrerequisite(numCourses int, prerequisites [][]int, queries [][]int) []bool {
	var (
		// 构建邻接表
		edges = make([][]int, numCourses)
		// 存储每个节点的先修课程节点
		preNodes = make([]map[int]bool, numCourses)
		// 存储入度表
		inDegree = make([]int, numCourses)
		// 存储查询结果
		answer = make([]bool, len(queries))
		// 将入度为0的节点存入queue
		queue []int
	)

	// 构建邻接表
	for _, info := range prerequisites {
		// info[0] -> info[1]
		edges[info[0]] = append(edges[info[0]], info[1])
		// 计算入度
		inDegree[info[1]]++
	}

	// 将入度为0的节点存入队列
	for i, v := range inDegree {
		if v == 0 {
			queue = append(queue, i)
		}
	}

	// BFS
	for len(queue) != 0 {
		e := queue[0]
		queue = queue[1:]
		// 遍历邻接节点
		for _, v := range edges[e] {
			// preNodes记录节点v的所有祖先节点（父亲/爷爷。。。。）
			preNodes[v] = mergeMap(preNodes[v], preNodes[e])
			preNodes[v][e] = true
			inDegree[v]--
			if inDegree[v] == 0 {
				queue = append(queue, v)
			}
		}
	}

	// 判断info[1]的先修课程info[0]是否存在
	for i, info := range queries {
		answer[i] = preNodes[info[1]][info[0]]
	}
	return answer
}

func mergeMap(target, src map[int]bool) map[int]bool {
	if target == nil {
		target = make(map[int]bool)
	}
	for k, v := range src {
		target[k] = v
	}
	return target
}

/*
floyd算法-判断节点i到j是否可达（或者计算节点i到j的最短路径）
时间复杂度：O(n^3) 三重循环，n为节点个数
空间复杂度：O(n^2) 邻接矩阵内存开销
*/
func checkIfPrerequisite1(numCourses int, prerequisites [][]int, queries [][]int) []bool {
	// 构建邻接矩阵（如果只求是否可达，则设置为[][]bool, 如果是带权值的有向图，则设置为[][]int）
	graph := make([][]bool, numCourses)
	for i := 0; i < numCourses; i++ {
		graph[i] = make([]bool, numCourses)
	}

	// 构造邻接矩阵
	for _, info := range prerequisites {
		// info[0] -> info[1]; 表示info[0]到info[1]的路径可达
		graph[info[0]][info[1]] = true
	}

	// floyd算法
	// 三层循环均遍历所有节点，最外层为k，表示i到j的路径中经过节点k的最短路径
	for k := 0; k < numCourses; k++ {
		for i := 0; i < numCourses; i++ {
			for j := 0; j < numCourses; j++ {
				// 如果节点i到k的路径可达，节点k到j的路径可达，则节点i到j的路径可达
				/*
					如果是计算最短路径权值，使用：
					if graph[i][j] > graph[i][k] + graph[k][j] {
						graph[i][j] = graph[i][k] + graph[k][j]
					}
				*/
				if graph[i][k] && graph[k][j] {
					graph[i][j] = true
				}
			}
		}
	}

	// 存储查询结果
	answer := make([]bool, len(queries))
	for i, info := range queries {
		answer[i] = graph[info[0]][info[1]]
	}
	return answer
}

// BFS-通过邻接矩阵判断是否可达
func checkIfPrerequisite2(numCourses int, prerequisites [][]int, queries [][]int) []bool {
	var (
		// 入度表
		inDegree = make([]int, numCourses)
		// 邻接矩阵（通过graph[i][j]是否为true判断i到j是否可达）
		graph  = make([][]bool, numCourses)
		queue  []int
		answer = make([]bool, len(queries))
	)

	for i := 0; i < numCourses; i++ {
		graph[i] = make([]bool, numCourses)
	}

	// 构造邻接矩阵
	for _, info := range prerequisites {
		// info[0] -> info[1]可达
		graph[info[0]][info[1]] = true
		// 记录入度
		inDegree[info[1]]++
	}

	// 将入度为0的节点存入队列
	for i, v := range inDegree {
		if v == 0 {
			queue = append(queue, i)
		}
	}

	// bfs
	for len(queue) > 0 {
		e := queue[0]
		queue = queue[1:]
		// 遍历e的所有邻接节点，在邻接矩阵中，graph[e]存储的是e到所有节点是否可达，只有当可达时才是e的邻接节点
		// 所以如果v不为true，则不是e的邻接节点，不能进行入度-1的操作
		for j, v := range graph[e] {
			if !v {
				continue
			}
			for i := 0; i < numCourses; i++ {
				// 由于e是j的先修节点，如果i是e的先修节点，则i一定是j的先修节点
				if graph[i][e] {
					graph[i][j] = true
				}
			}
			inDegree[j]--
			if inDegree[j] == 0 {
				queue = append(queue, j)
			}
		}
	}

	for i, q := range queries {
		answer[i] = graph[q[0]][q[1]]
	}
	return answer
}
